package org.leetcode.middle.leetcode90;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution
{
    List<List<Integer>> res =  new ArrayList<>();

    List<Integer> item = new ArrayList<>();
    LinkedList<Integer> temp = new LinkedList<>();

    boolean [] used;

    public List<List<Integer>> subsetsWithDup2(int[] nums) {

        if (nums.length==0)
        {
            res.add(temp);
            return res;
        }
        Arrays.sort(nums);
        used = new boolean[nums.length];
        subsetsWithDupHelper(nums,0);
        return res;
    }

    private void backtracking2(int [] nums,int startIndex){
        res.add(new ArrayList<>(item));
        if (startIndex>=nums.length){
            return;
        }

        for (int i = startIndex; i < nums.length; i++) {
            if (i>0 && nums[i]==nums[i-1] && !used[i-1]){
                continue;
            }
            item.add(nums[i]);
            used[i] =true;

            backtracking2(nums,i+1);

            item.remove(item.size()-1);
            used[i]=false;
        }
    }


    private void subsetsWithDupHelper(int []nums,int startIndex)
    {
        res.add(new ArrayList<>(temp));

        if (startIndex>nums.length-1)
        {
            return;
        }

        for (int i = startIndex; i <nums.length; i++) {

            //排序后的数组，前一个相同的数，没被用到，说明是回溯，需要跳过
            if (i>0 && nums[i]==nums[i-1] && !used[i-1])
            {
                continue;
            }

            temp.addLast(nums[i]);
            used[i]=true;

            subsetsWithDupHelper(nums,i+1);

            temp.removeLast();
            used[i]=false;
    }

    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        Arrays.sort(nums);
        backtracking(nums,0);
        return res;
    }

    private void backtracking(int [] nums,int startIndex)
    {
        res.add(new ArrayList<>(temp));

        for (int i = startIndex; i <nums.length; i++) {

            temp.addLast(nums[i]);

            backtracking(nums,i+1);

            temp.removeLast();

            //去重操作
            while (i < nums.length -1 && nums[i] == nums[i+1])
                i++;
        }

    }
}
